# !/usr/bin/env python
# -*- coding: utf-8 -*-

# 希尔排序
# 基本思想：将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；
# 然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。

# 时间复杂度:O(n^(1.3-2))
# 空间复杂度:最好0(已经排好序),最坏O(n)(逆序),平均O(1)
# 稳定性:不稳定
from sort.arr_util import random_scale_arr


def shell_sort(num_arr):
    length = len(num_arr)
    gap = int(length/2)
    while gap > 0:
        for i in range(gap, length):
            tmp = num_arr[i]
            j = i
            while j >= gap and tmp < num_arr[j - gap]:
                num_arr[j] = num_arr[j - gap]
                j -= gap
            num_arr[j] = tmp
        gap = int(gap / 2)


if __name__ == '__main__':
    arr = [1, 2, 5, 7, 6, 5, 4]
    shell_sort(arr)
    print(arr)
    arr2 = random_scale_arr(20, 500)
    shell_sort(arr2)
    print(arr2)
